Detection of overlapping communities in complex networks has motivated recentresearch in the relevant fields. Aiming this problem, we propose a Markovdynamics based algorithm, called UEOC, which means, 'unfold and extractoverlapping communities'. In UEOC, when identifying each natural community thatoverlaps, a Markov random walk method combined with a constraint strategy,which is based on the corresponding annealed network (degree conserving randomnetwork), is performed to unfold the community. Then, a cutoff criterion withthe aid of a local community function, called conductance, which can be thoughtof as the ratio between the number of edges inside the community and thoseleaving it, is presented to extract this emerged community from the entirenetwork. The UEOC algorithm depends on only one parameter whose value can beeasily set, and it requires no prior knowledge on the hidden communitystructures. The proposed UEOC has been evaluated both on synthetic benchmarksand on some real-world networks, and was compared with a set of competingalgorithms. Experimental result has shown that UEOC is highly effective andefficient for discovering overlapping communities.
展开▼
